//
// Created by ASUS on 2024/5/8/星期三.
//
#include <bits/stdc++.h>
using namespace std;
//O(nlogn)
int lengthOfLIS(vector<int>& nums) {
	int n=nums.size();
	vector<int> f={nums[0]};
	for(int i=1;i<n;i++){
		if(nums[i]>f.back()) f.push_back(nums[i]);
		else *lower_bound(f.begin(),f.end(),nums[i])=nums[i];
	}
	return f.size();
}